class Solution:
    def mySqrt(self, x: int) -> int:
        start ,end = 0,x
        ans = -1
        while start <= end:
            mid = (start + end) //2
            #print(mid)
            if mid**2 > x:
                end = mid-1
            else:
                ans = mid
                start = mid+1

        return ans

    def mySqrt2(self, x: int) -> int:
        l, r, ans = 0, x, -1
        while l <= r:
            mid = (l + r) // 2
            if mid * mid <= x:
                ans = mid
                l = mid + 1
            else:
                r = mid - 1
        return ans






if __name__ == '__main__':
    x  = 4
    solution = Solution()
    val = solution.mySqrt(x)
    print(val)
